
#include "kmp_string.h"

void kmp_init(kmp_string_t *s)
{
    int i, j;


    if (s == NULL || s->pattern == NULL || s->prefix_tbl == NULL || s->pattern_len == 0)
        return ;


    // init matched
    s->matched = 0;

    // init prefix table
    s->prefix_tbl[0] = 0;

    for (i = 1, j = 0; i < s->pattern_len; i++)
    {
        while (j > 0 && s->pattern[j] != s->pattern[i])
            j = s->prefix_tbl[j - 1];

        if (s->pattern[j] == s->pattern[i])
            j++;

        s->prefix_tbl[i] = j;
    }
}

int  kmp_find(kmp_string_t *s, const char c)
{
    if (s == NULL || s->pattern == NULL || s->prefix_tbl == NULL || s->pattern_len == 0)
        return 0;

    while (s->matched > 0 && c != s->pattern[s->matched])
        s->matched = s->prefix_tbl[s->matched - 1];

    if (c == s->pattern[s->matched])
        s->matched++;

    // check if all matched
    if (s->matched == s->pattern_len)
    {
        // clear matched count if all pattern is matched
        s->matched = 0;
        return s->pattern_len;
    }

    return s->matched;
}

void  kmp_reset(kmp_string_t *s)
{
    if (s == NULL || s->pattern == NULL || s->prefix_tbl == NULL || s->pattern_len == 0)
        return ;

    s->matched = 0;
}
